/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/3sum
   @Language: C++
   @Datetime: 16-02-09 05:41
   */

class Solution {	
public:
	/**
	 * @param numbers : Give an array numbers of n integer
	 * @return : Find all unique triplets in the array
	 *           which gives the sum of zero.
	 *           each triplet in non-descending order
	 */
	/** Tips : Sort the Array in ascending order
	 *  step 1 : we can fix the first element i,
	 *           and find the other two in range [i+1,end)
	 *  step 2 : find the other two, using binary search likely because
	 *           the array is in ascending order
	 *           we can use two point j and k:
	 *           that j from i+1 to end, k from end to j
	 *           
	 *  notice : Attention for duplication
	 *
	 * sketch :
	 * array in ascending order:
	 *        -3   1   1   2   3
	 *         |   |           |
	 *         i   j           k
	 * current A[i]+A[j]+A[k] > 0, so move k to k-1
	 *         if current triplet's sum < 0, move j to j+1
	 * */
	vector<vector<int> > threeSum(vector<int> &A) {
		// write your code here
		vector<vector<int> > vs;
		int target = 0;
		sort(A.begin(),A.end());    // sort A in ascending order
		for(int i=0; i<A.size(); ++i){
			if (i>0 && A[i-1]==A[i]) continue;        // skip duplication
			for(int j=i+1, k=A.size()-1; j<k;){
				if (j>i+1 && A[j-1]==A[j]){
					++j;
					continue;       // skip duplication
				}
				if (k<A.size()-1 && A[k]==A[k+1]){
					--k;
					continue;       // skip duplication
				}
				int sum = A[i]+A[j]+A[k];
				if (sum > target) --k;
				else if (sum < target) ++j;
				else{               // find a triplet
					vector<int> v(3,A[i]);
					v[1] = A[j++];
					v[2] = A[k--];
					vs.push_back(v);
				}
			}
		}
		return vs;
	}
};
